|
11.17 As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node's depth as a potential function.
a. What is the maximum value of the potential function? b. What is the minimum value of the potential function? c. The difference in the answers to parts ( a) and ( b) gives some indication that this potential function isn't too goo d. Show that a splaying operation could increase the potential by (N/ logN). - | |
| View Solution | |
| << Back | |